BOJ_11055_가장 큰 증가하는 부분 수열

LIS(Longest Increasing Subsequence) 알고리즘을 사용해서 푸는 문제

LIS를 dp로 풀어내는 전형적인 유형이지만, 길이가 아니라 합이 최대인 수열을 구한다는 것이 조금 차이가 있다
하지만 문제를 풀어내는 데에는 크게 다르지 않다

누적합을 구해야 하기 때문에 dp배열을 dp[i] = nums[i]로 초기화 한 후,
N개의 수열을 돌면서 0~i-1 인덱스의 dp를 확인하며 갱신한다
이 dp 배열에서 가장 큰 값이 정답이 된다

# LIS를 사용하는 문제  
  
N = int(input())  
nums = list(map(int, input().split()))  
dp = [0] * (N + 1)  
for i in range(N):  
    dp[i] = nums[i]  
  
for i in range(N):  
    for j in range(0, i):  
        if nums[i] > nums[j]:  
            dp[i] = max(dp[i], dp[j] + nums[i])  
  
print(max(dp))